package com.tiny.work.leetcode;

import org.junit.Test;

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.core.Is.is;

public class UniqueBinarySearchTrees {
    public int numTrees(int n) {
        if (n<=0) {
            return 0;
        }
        if (n==1 || n==0) {
            return 1;
        }

        int result[] = new int[n+1];
        result[0]=result[1]=1;
        for (int i=2; i<=n; i++){
            for (int j=0; j<i;j++) {
                result[i] += result[j] * result[i-j-1];
            }
        }
        return result[n];
    }
    @Test
    public void test(){
        assertThat(numTrees(3), is(5));
//        assertThat(numTrees(4), is(5));
//        assertThat(numTrees(5), is(5));
    }
}
